/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/first-unique-character-in-a-string
   @Language: C++
   @Datetime: 19-03-17 11:52
   */

class Solution {
public:
	/**
	 * @param str: str: the given string
	 * @return: char: the first unique character in a given string
	 */
	char firstUniqChar(string &str) {
		// Write your code here
		int dict[128][2], ch=0;   // count, index
		memset(dict, 0, sizeof(dict));
		dict[0][1] = str.length();
		for(int i=0; i<str.length(); ++i){
			if (dict[str[i]]==0) dict[str[i]][1]=i;
			dict[str[i]][0]++;
		}
		for(int i=0; i<128; ++i)
			if (dict[i][0]==1 && dict[i][1]<dict[ch][1]) ch=i;
		return ch;
	}
};
